/*
输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 */
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
// class Solution
// {
// public:
//     void swap(string &s, int a, int b)
//     {
//         char temp = s[a];
//         s[a] = s[b];
//         s[b] = temp;
//     }
//     vector<string> permutation(string s)
//     {
//         set<string> ans;
//         comb(ans, s, 0);
//         vector<string> result;
//         for (auto i = ans.begin(); i != ans.end(); i++)
//         {
//             result.push_back(*i);
//         }

//         return result;
//     }
//     void comb(set<string> &ans,  string &s, int index)
//     {
//         if (index == s.size())
//         {
//             ans.insert(s);
//         }
//         int len = s.size();
//         for (int i = index; i < len; i++)
//         {
//             swap(s, index, i);
//             comb(ans, s, index + 1);
//             swap(s, index, i);
//         }
//     }
// };

// leetcode 官方题解。一个字符一个字符组成答案。排序+组合+规避重复
class Solution
{
public:
    vector<string> rec;
    vector<int> vis;

    void backtrack(const string &s, int i, int n, string &perm)
    {
        if (i == n)
        {
            rec.push_back(perm);
            return;
        }
        for (int j = 0; j < n; j++)
        {
            // 相同字符必须按照从左到右的顺序放入。
            if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j]))
            {
                continue;
            }
            vis[j] = true;
            perm.push_back(s[j]);
            backtrack(s, i + 1, n, perm);
            perm.pop_back();
            vis[j] = false;
        }
    }

    vector<string> permutation(string s)
    {
        int n = s.size();
        vis.resize(n);
        sort(s.begin(), s.end());
        string perm;
        backtrack(s, 0, n, perm);
        return rec;
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    string str = "kzfxxx";
    vector<string> ans = s.permutation(str);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}
